package nachos.threads;

import nachos.machine.*;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Vector;

/**
 * A scheduler that chooses threads using a lottery.
 *
 * <p>
 * A lottery scheduler associates a number of tickets with each thread. When a
 * thread needs to be dequeued, a random lottery is held, among all the tickets
 * of all the threads waiting to be dequeued. The thread that holds the winning
 * ticket is chosen.
 *
 * <p>
 * Note that a lottery scheduler must be able to handle a lot of tickets
 * (sometimes billions), so it is not acceptable to maintain state for every
 * ticket.
 *
 * <p>
 * A lottery scheduler must partially solve the priority inversion problem; in
 * particular, tickets must be transferred through locks, and through joins.
 * Unlike a priority scheduler, these tickets add (as opposed to just taking
 * the maximum).
 */
public class LotteryScheduler extends Scheduler {
	//varblock++++++

	public static final int priorityMaximum = Integer.MAX_VALUE;
	public static final int priroityDefault = 1;
	public static final int priorityMinimum = 1;
	//==============

	//constructor==========================================
	// all the bs asssiated with making a new scheduler and
	// book-keeping stuffs - new threadstate/queue
	//-----------------------------------------------------
	public LotteryScheduler() {
	}

	protected ThreadState getThreadState(KThread thread) {
		if (thread.schedulingState == null) {
			thread.schedulingState = new ThreadState(thread);
		}
		return (ThreadState) thread.schedulingState;
	}

	public ThreadQueue newThreadQueue(boolean transferPriority) {
		return new LoteryQueue(transferPriority);
	}

	//priority manipulation++++++++++++++++++++++++++++++++
	public int getPriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getPriority();
	}

	public int getEffectivePriority(KThread thread) {
		Lib.assertTrue(Machine.interrupt().disabled());

		return getThreadState(thread).getEffectivePriority();
	}

	public void setPriority(KThread thread, int priority) {
		Lib.assertTrue(Machine.interrupt().disabled());

		Lib.assertTrue(priority >= priorityMinimum
			&& priority <= priorityMaximum);

		getThreadState(thread).setPriority(priority);
	}

	public boolean increasePriority() {
		boolean intStatus = Machine.interrupt().disable();
		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if (priority == priorityMaximum) {
			return false;
		}

		setPriority(thread, priority + 1);

		Machine.interrupt().restore(intStatus);
		return true;
	}

	public boolean decreasePriority() {
		boolean intStatus = Machine.interrupt().disable();

		KThread thread = KThread.currentThread();

		int priority = getPriority(thread);
		if (priority == priorityMinimum) {
			return false;
		}

		setPriority(thread, priority - 1);

		Machine.interrupt().restore(intStatus);
		return true;
	}
	//=====================================================

	//thread queue=========================================
	// next thread is determined by how many tickets a thread
	// has.  a queue keeps track of how many tickets are
	// in line.  We get a random number from 0 to numTickets
	// then iiterate through the list and subract the threads
	// priority from the number.  Once the rNum is less than
	// or equal to 0, we return that thread.
	//-----------------------------------------------------
	protected class LoteryQueue extends ThreadQueue {
		//var block-----------
		ThreadState owner;
		protected boolean transferPriority;
		protected LinkedList<ThreadState> queue;
		//====================

		public LoteryQueue(boolean _transferPriority) {
			transferPriority = _transferPriority;
			queue = new LinkedList<ThreadState>();
		}

		protected int tickets() {
			int temp = 0;
			for (ThreadState st : queue) {
				temp += st.getEffectivePriority();
			}
			return temp;
		}

		public KThread nextThread() {
			Lib.assertTrue(Machine.interrupt().disabled());

			if (owner != null) {
				owner.acquired.remove(this);
			}
			if (queue.isEmpty()) {
				return null;
			}
			int rNum = Lib.random(tickets());
			Iterator<ThreadState> iter = queue.iterator();
			ThreadState handle = iter.next();
			while (rNum > 0 && iter.hasNext()) {
				handle = iter.next();
				rNum -= handle.getEffectivePriority();
			}
			queue.remove(handle);
			owner = handle;
			acquire(handle.thread);
			return handle.thread;
		}

		public void waitForAccess(KThread thread) {
			getThreadState(thread).waitForAccess(this);
			queue.push(getThreadState(thread));
		}

		public void acquire(KThread thread) {
			Lib.assertTrue(Machine.interrupt().disabled());
			getThreadState(thread).acquire(this);
		}

		public void print() {
			Lib.assertTrue(Machine.interrupt().disabled());
			System.out.println("Queue Contents-------------"+transferPriority+"\\");
			System.out.println("Tickets: " + tickets());
			if (owner != null) {
				System.out.println("Owner: " + owner.thread.getName() + "--" + owner.getPriority() + "--" + owner.getEffectivePriority() + "--:" + owner.acquired.size());
			}
			for (ThreadState ts : queue) {
				System.out.println(ts.thread.getName() + " -- " + ts.getPriority() + " -- " + ts.getEffectivePriority());
			}
			System.out.println("----------------------------/");
		}
	}
	//=====================================================
	//ThreadState++++++++++++++++++++++++++++++++++++++++++

	protected class ThreadState {
		//varblock--------

		protected KThread thread;
		protected int priority;
		protected int epriority;
		boolean refresh;
		protected Vector<LoteryQueue> acquired;
		//----------------
		//constructors=================================
		// the constructor keeps track of the thread
		// param
		//---------------------------------------------

		public ThreadState(KThread _thread) {
			priority = LotteryScheduler.priroityDefault;
			refresh = true;
			thread = _thread;
			acquired = new Vector<LoteryQueue>();
		}
		//=============================================

		//priority access==============================
		// used to access the real priority and the
		// inherited priority.  tryes to cache the
		// epriority so that it need'nt be recalculated
		// every time.  updated if priority is changed
		// and when it recieves/looses ownership
		//---------------------------------------------
		public int getEffectivePriority() {
			if (true) {
				epriority = 0;
				LoteryQueue q;
				for (int i = 0; i < acquired.size(); i++) {
					q = acquired.get(i);
					if (q.transferPriority) {
						epriority += q.tickets();
					}
				}
			}
			refresh = false;
			return priority + epriority;
		}

		public int getPriority() {
			return priority;
		}

		public void setPriority(int _priority) {
			priority = _priority;
			refresh = true;
		}
		//=============================================

		public void acquire(LoteryQueue queue) {
			acquired.add(queue);
		}

		public void waitForAccess(LoteryQueue queue) {
		}
	}
	//======================================================
}
